In some communication networks, data may be transmitted and/or stored within data storage devices with redundancy information. Redundancy information may be utilized to determine the integrity of data received via the communication network, or retrieved from the storage device. Determination of data integrity may comprise a set of operations, which enable detection and/or correction of bit errors in the received data or retrieved data.
For example, the data may be transmitted within a packet, which may comprise a header, payload and/or trailer. The data may be contained within the payload, while redundancy information may be contained within the header and/or trailer. An example of redundancy information is a length field, which may indicate a length, as measured in octets, of the payload. Another example of redundancy information is a cyclic redundancy check (CRC) field. At a transmitter, the CRC may be computed for the bits contained in at least the payload based on a generator polynomial. The computed CRC value may be inserted in the header and/or payload of the packet. A receiver of the packet may utilize the CRC to determine whether there are bit errors in the received packet. In addition, the CRC may enable correction of detected bit errors in the received packet. The receiver may also utilize the length field to determine whether the length of the received payload is correct.
In many communication systems, the data contained within the payload is not raw data, but encoded raw data, or encoded data. Encoded data may be generated from raw data by utilizing forward error correction (FEC), for example. Within a transmitter, or other data encoding source device, encoded data may be generated from raw data by utilizing an encoding algorithm, such as one from the class of FEC code algorithms. Exemplary error correcting code algorithms include convolutional coding algorithms. Convolutional coding algorithms generate m bits of encoded data from n bits of raw data where typically m>n. The ratio n/m may be referred to as a coding rate for the convolutional coding algorithm. Thus, a total of N bits of raw data may be encoded to generate a total of M bits of encoded data within a payload. The M bits of encoded data may correspond to a payload length of M/8 octets, for example. The m bits of encoded data may comprise (m−n) bits of redundancy information that may be utilized at a receiver, or other data destination device, to detect and/or correct errors in received data or retrieved data. Prior to transmission, the encoded data bits may be modulated to form symbols. Each symbol may be a representation of one or more encoded data bits. For example, with 8 phase shift keying (8-PSK) modulation, each symbol may represent 3 encoded data bits. The transmitted signals may comprise a plurality of symbols.
At a receiver the received symbols may be demodulated to recover at least estimated values for the encoded data, which was modulated by the transmitter, or other data source device. The demodulation method used at the receiver, or other data destination device, typically corresponds to the modulation method used at the transmitter, or other data source device. For example, if a transmitter modulated encoded data utilizing 8-PSK modulation, a receiver may demodulate the received signals utilizing 8-PSK demodulation.
At a receiver, or other data destination device, the encoded data may be decoded to extract at least estimates of the binary values contained in the raw data, which was previously processed within the transmitter, or other data source device, to generate the encoded data. Within the receiver, or other data destination device, a decoding algorithm may be utilized to generate the estimated raw data from the estimated encoded data. Exemplary decoding algorithms include the Viterbi algorithm, maximum likelihood sequence estimation (MLSE) and the maximum a posteriori probability (MAP) algorithm. The application of the Viterbi algorithm to estimated encoded data may be referred to as Viterbi decoding.
With Viterbi decoding, a set of logic states is defined wherein each potential symbol value corresponds to one of the logical states. Then a state transition diagram is defined for a set of time instants within a time window, wherein each time instant corresponds to reception of, or retrieval of, a symbol. The state transition diagram specifies which subsequent states are possible at a succeeding time instant given a current state and a current time instant. Each state transition may be referred to as an arc. An estimated value for a subsequent received symbol is compared with the values corresponding to each of the subsequent states. The comparison is typically a computed Hamming distance, or Euclidean distance, between the estimated symbol value and each state value, for example. The comparison may be based on computed Euclidean distances when the symbol values have not been demodulated, such as in soft-decision decoding. The comparison may be based on computed Hamming distances when symbol values have been demodulated, such as in hard-decision decoding. Each comparison may enable computation of an error metric. Consequently, each arc may be associated with a corresponding error metric.
Across the span of a time window, from the first time instant to the last time instant, a plurality of state transition arcs may be defined. Each arc may define a distinct set of state transitions across the span of the time window. Associated with each arc is an aggregated error metric, which is computed as a sum of the error metrics at each time instant along the arc. Among the plurality of state transition arcs, a state transition arc, which has the lowest aggregated error metric value, may be selected. The selected state transition arc may be utilized to derive the estimated raw data.
MLSE decoding is similar to Viterbi decoding, however, with MLSE decoding, an error metric is computed for the state transition arc from each state at a current time instant, to each state at a succeeding time instant. Thus, for a state transition diagram in which there are four defined states, a total of 16 arcs may be defined for each time instant, for which a corresponding 16 error metrics may be computed. A state transition arc across the time window may be constructed by selecting a state at each time instant, which is associated with the minimum error metric at that time instant. In this regard, MLSE decoding may be considered to be a brute-force computational alternative to Viterbi decoding.
With MAP decoding, each subsequent state transition is considered to be a random variable, such as may be computed in Bayesian statistics, wherein the likelihood of a succeeding state transition, following a current time instant, may be determined after making observations of preceding state transitions.
After decoding the received, or retrieved, symbols to derive raw data, the redundancy information in the packet header and/or trailer may then be utilized to determine the integrity of the decoded data. The length field, for example, may be utilized to determine whether the length of the decoded data field is correct. The CRC may be utilized to determine whether there are bit errors in the decoded data.
One limitation associated with the redundancy information is that while the redundancy information may enable detection of bit errors in the decoded data, it may not enable correction of the bit errors. Consequently, an inability to correct detected bit errors in received, or retrieved, packets may result in lost data if the received, or retrieved, packet is discarded due to the detected error(s).
Further limitations and disadvantages of conventional and traditional approaches will become apparent to one of skill in the art, through comparison of such systems with some aspects of the present invention as set forth in the remainder of the present application with reference to the drawings.